This invention relates generally to decreasing the number of computations that need to be done in a computer system, and more particularly to using memoization to reduce the number of computations.
The term xe2x80x9cmemoizationxe2x80x9d is known in the field of computer science as a technique for recording and remembering the results of previous computations so that repeating the same computations can be avoided, see Field et al., in xe2x80x9cMemoization,xe2x80x9d Addison-Wesley Publishing Company Functional Programming, Chapter 19, pp. 505-506, 1988. The term comes from the word xe2x80x9cmemoxe2x80x9dxe2x80x94xe2x80x9cA short note written as a reminder,xe2x80x9d The American Heritage Dictionary of the English Language, 1970, American Heritage Publishing. Memorization techniques have also been used to save results of data dependence tests in order to avoid calling data dependence routines multiple times for the same input. See, Dror Maydan, et al., in xe2x80x9cEfficient and Exact Data Dependence Analysis,xe2x80x9d Proceedings of the ACMSIGPLAN 1991.
For example, it is desired to compute the Fibonacci numbers using the following simple program:
fib(n) {
if n is 1 or 2, return 1;
return fib(nxe2x88x921)+fib(nxe2x88x922);
}
A method 100 for performing this computation is shown in FIG. 1. The input parameters (I) are provided in step 110. The computation itself (F) is done in step 120, and the result (R) is provided in step 130. Because fib( ) is recomputed over and over for the same argument, run time for the above method is O(1.6n).
A more complex program computes the Fibonacci numbers as follows:
allocate array for memo, initializing all elements to zero initialize memo[1] and memo[2] to 1;
fib(n) {
if memo[n] is not zero, return memo[n];
memo[n]=fib(nxe2x88x921) +fib(nxe2x88x922);
return memo[n];
}
When the value of fib(n) is memoized, the run time is reduced and becomes O(1) if n is in the memo and O(n) if n is not in the memo.
FIG. 2 shows how memoization is used to speed up the method. As above input 210 is provided in step 210. Step 215 determines whether a result (R) for this particular input (I) is contained in a memo 216. If true, the memo is read and the result (R) is provided in step 230. Otherwise, if false, compute the result (R). in step 220, memoize the result in the memo, and provide the result in step 230.
The problem with this method is that the input must exactly match what is contained in the memo, that is the memo is limited to storing and producing discrete values, and thus the prior art memoization method has limited utility. The need remains to provide a more efficient and versatile memoization method.
A method memoizes a computation as follows. A set of input parameters are provided to the computation. A determination is made to see whether a memo contains results of the computation on sets of memoized parameters near the set of input parameters. If true, the computation for the set of input parameters is reconstructed using the results of the computations on the sets of memoized parameters near the set of input parameters. If false, the computation is performed using the set of input parameters. A result of the computation on the set of input parameters is then memoized, and that result is provided as output of the computation.
Reconstruction can be done by applying some continuous function, such as interpolation, on the memoized results. Additionally, the computation can be partitioned into a number of partial computations, and only selected partial computations are memoized.